
//编程实现删除一个数组中的重复元素,数组是正整数数组
// 可以设置一个flag = 0;
// 通过两重循环，找到重复元素，就标志flag
//通过一次移动实现


#include <iostream>

using namespace std;


//构造一个顺序表
class SList
{
private:
    int * elems;
    int length;
    int capacity;
public:
    SList(int capacity):capacity(capacity),length(0)
    {
        elems = new int[this->capacity];
    }
    SList():capacity(10),length(0)
    {
        elems = new int[this->capacity];
    }

    //通过数组构造顺序表
    int init(int arr[],int n)
    {
        if(n>capacity)
        {
            //重新分配内存
            int *base = new int[n];
            if(base==NULL)
            {
                return 0 ; //分配失败
            }
            this->elems = base;
            //释放base
            delete[] base;
            base = NULL;

            //更新capacity
            this->capacity = n;
        }

        //构造
        for(int i = 0;i<n;i++)
        {
            this->elems[i] = arr[i];
        }
        this->length = n;
    }

    int getLength()
    {
        return this->length;
    }
    int getCapacity()
    {
        return this->capacity;
    }

    void show()
    {
        cout<<"显式元素"<<endl;
        for(int i = 0;i<this->length;i++)
        {
            cout<<this->elems[i]<<",";
        }

    }

    void markElem(int flag)  //使用flag标记
    {
        for(int i = 0;i<this->length;i++)
        {
            for(int j=i+1;j<this->length;j++)
            {
                if(this->elems[i]==this->elems[j])
                {
                    this->elems[j] = flag;
                }
            }
        }
    }

    //删除重复元素
    void delElems(int flag)
    {
        int i = 0;
        int j = i;
        this->markElem( flag);
        while(j<this->length)
        {
            if(this->elems[i]==flag)
            {
                while(this->elems[j]==flag)
                {
                    j++;
                }
                this->elems[i]=this->elems[j];
                this->elems[j]=flag;
                i++;

            }
            if(this->elems[i]!=flag)
            {
                i++;
                j++;
            }
        }
        this->length=i-1;
    }

    ~ SList()
    {
        if(this->elems !=NULL)
        {
            delete[] elems;
            elems = NULL;
        }
    }
};


int main()
{
    int arr[10] = {1,2,2,2,3,4,2,5,2,5};
    SList my_list = SList();
    my_list.init(arr,10);
    my_list.show();

    //标记
    //my_list.markElem(0);
    //删除重复元素
    my_list.delElems(0);
    my_list.show();
    system("pause");
    return 0;
}
